/**
 * 399. 除法求值
 * https://leetcode-cn.com/problems/evaluate-division/
 */
const { displayBaseArray } = require('../../libs/public');

/**
 * @param {Map<string, Map<string, number>>} relations
 * @param {string} x1
 * @param {string} x2
 * @param {Set<string>} searched
 * @return {number}
 */
function calculate(relations, x1, x2, searched) {
  const relation1 = relations.get(x1);
  if (relation1.has(x2)) {
    return relation1.get(x2);
  }
  if (searched.has(x1)) {
    return -1;
  }
  searched.add(x1);
  // eslint-disable-next-line no-restricted-syntax
  for (const [key, value] of relation1) {
    const res = calculate(relations, key, x2, searched);
    if (res >= 0) {
      return value * res;
    }
  }
  return -1;
}

/**
 * @param {string[][]} equations
 * @param {number[]} values
 * @param {string[][]} queries
 * @return {number[]}
 */
function calcEquation(equations, values, queries) {
  const relations = new Map();
  const vars = new Set();
  for (let i = 0; i < equations.length; i += 1) {
    const [x1, x2] = equations[i];
    let relation = relations.get(x1);
    if (!relation) {
      relation = new Map();
      relations.set(x1, relation);
    }
    relation.set(x2, values[i]);

    relation = relations.get(x2);
    if (!relation) {
      relation = new Map();
      relations.set(x2, relation);
    }
    relation.set(x1, 1 / values[i]);

    vars.add(x1);
    vars.add(x2);
  }
  const result = new Array(queries.length).fill(-1);
  for (let i = 0; i < queries.length; i += 1) {
    const [x1, x2] = queries[i];
    if (!vars.has(x1) || !vars.has(x2)) {
      continue;
    }
    if (x1 === x2) {
      result[i] = 1;
      continue;
    }
    result[i] = calculate(relations, queries[i][0], queries[i][1], new Set());
  }
  return result;
}

console.log(displayBaseArray(calcEquation(
  [['a', 'b'], ['b', 'c']],
  [2.0, 3.0],
  [['a', 'c'], ['b', 'a'], ['a', 'e'], ['a', 'a'], ['x', 'x']],
)) === '[6,0.5,-1,1,-1]');
console.log(displayBaseArray(calcEquation(
  [['a', 'b'], ['b', 'c'], ['bc', 'cd']],
  [1.5, 2.5, 5.0],
  [['a', 'c'], ['c', 'b'], ['bc', 'cd'], ['cd', 'bc']],
)) === '[3.75,0.4,5,0.2]');
console.log(displayBaseArray(calcEquation(
  [['a', 'b']],
  [0.5],
  [['a', 'b'], ['b', 'a'], ['a', 'c'], ['x', 'y']],
)) === '[0.5,2,-1,-1]');
